#ifndef _FIND_
#define _FIND_

#include <set>
#include <vector>
using namespace std;

class Find {
public:
    // my solution
    int findRepeatNumber( vector< int >& nums ) {
        vector< int > temp( nums.size(), -1 );

        for ( size_t i = 0; i < nums.size(); i++ ) {

            int pos = nums.at( i );

            if ( temp.at( pos ) != -1 ) {
                return temp.at( pos );
            }

            temp.at( pos ) = pos;
        }
        return -1;
    }

    // set
    int findRepeatNumber2( vector< int >& nums ) {
        set< int > s;

        pair< set< int >::iterator, bool > ret;

        for ( size_t i = 0; i < nums.size(); i++ ) {

            ret = s.insert( nums.at( i ) );

            if ( ret.second == false ) {
                return nums.at( i );
            }
        }
        return -1;
    }

    // time o(n) space o(1)
    int findRepeatNumber3( vector< int >& nums ) {
        int n = nums.size();
        for ( int i = 0; i < n; i++ ) {
            int k = nums[ i ];
            if ( k < 0 )
                k += n;
            if ( nums[ k ] < 0 )
                return k;
            nums[ k ] -= n;
        }
        return -1;
    }

    // traverse
    int search( vector< int >& nums, int target ) {
        int n = 0;
        for ( size_t i = 0; i < nums.size(); i++ ) {
            if ( nums[ i ] == target ) {
                n++;
            }
        }
        return n;
    }

    // binary search
    int search2( vector< int >& nums, int target ) {

        int leftPos = 0, rightPos = nums.size() - 1;
        int medium;
        int mdeiumValue;

        // find left position
        while ( leftPos <= rightPos ) {
            medium      = ( leftPos + rightPos ) / 2;
            mdeiumValue = nums[ medium ];
            if ( mdeiumValue > target ) {
                rightPos = medium - 1;
            }
            else if ( mdeiumValue == target ) {
                rightPos = medium - 1;
            }
            else if ( mdeiumValue < target ) {
                leftPos = medium + 1;
            }
        }
        int j    = leftPos;
        rightPos = nums.size() - 1;
        // find right position
        while ( leftPos <= rightPos ) {
            medium      = ( leftPos + rightPos ) / 2;
            mdeiumValue = nums[ medium ];
            if ( mdeiumValue > target ) {
                rightPos = medium - 1;
            }
            else if ( mdeiumValue == target ) {
                leftPos = medium + 1;
            }
            else if ( mdeiumValue < target ) {
                leftPos = medium + 1;
            }
        }

        return rightPos - j + 1;
    }

    // my solution
    int missingNumber( vector< int >& nums ) {
        int add = 0;
        for ( size_t i = 1; i <= nums.size(); i++ ) {
            add += i;
            add -= nums[ i - 1 ];
        }
        return add;
    }

    /*  binary search
        排序数组中的搜索问题，首先想到 二分法 解决。
        根据题意，数组可以按照以下规则划分为两部分。
        左子数组： nums[i]=i ；     右子数组： nums[i] ！=i ；
        缺失的数字等于 “右子数组的首位元素” 对应的索引；
    */
    int missingNumber2( vector< int >& nums ) {

        int low = 0, high = nums.size() - 1;
        int medium;

        while ( low <= high ) {

            medium = ( low + high ) / 2;
            if ( nums[ medium ] == medium ) {
                low = medium + 1;
            }
            else {
                high = medium - 1;
            }
        }
        return low;
    }

    // TRAVERSE
    bool findNumberIn2DArray( vector< vector< int > >& matrix, int target ) {
        int row = matrix.size();
        if ( row == 0 ) {
            return false;
        }
        int column = matrix[ 0 ].size();
        if ( column == 0 ) {
            return false;
        }

        for ( int i = 0; i < row; i++ ) {
            for ( int j = 0; j < column; j++ ) {
                if ( matrix[ i ][ j ] == target ) {
                    return true;
                }
            }
        }
        return false;
    }

    /* binary search O(MlogN) O(NlogM)
    由于矩阵 matrix 中每一行的元素都是升序排列的，因此我们可以对每一行都使用一次二分查找.
    */
    bool findNumberIn2DArray2( vector< vector< int > >& matrix, int target ) {

        int row = matrix.size();
        if ( row == 0 ) {
            return false;
        }
        int column = matrix[ 0 ].size();
        if ( column == 0 ) {
            return false;
        }

        for ( int i = 0; i < row; i++ ) {
            int low  = 0;
            int high = matrix[ i ].size() - 1;

            while ( low <= high ) {
                int mid = ( low + high ) / 2;

                if ( matrix[ i ][ mid ] == target ) {
                    return true;
                }
                else if ( matrix[ i ][ mid ] < target ) {
                    low = mid + 1;
                }
                else if ( matrix[ i ][ mid ] > target ) {
                    high = mid - 1;
                }
            }
        }

        /*
         for ( const auto& row : matrix ) {
            auto it = lower_bound( row.begin(), row.end(), target );
            if ( it != row.end() && *it == target ) {
                return true;
            }
        }
        */

        return false;
    }

    /*Z字形查找  O(M+N)
    我们可以从矩阵 matrix 的右上角 (0,n−1) 进行搜索。
    在每一步的搜索过程中，如果我们位于位置(x,y)，那么我们希望在以matrix 的左下角为左下角、以(x,y) 为右上角的矩阵中进行搜索，即行的范围为 [x,m−1]，列的范围为 [0,y]：

    如果 matrix[x,y]=target，说明搜索完成；

    如果 matrix[x,y]>target，由于每一列的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 y 列的元素都是严格大于 target 的，
    因此我们可以将它们全部忽略，即将y 减少 1；

    如果 matrix[x,y]<target，由于每一行的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 x 行的元素都是严格小于 target 的，
    因此我们可以将它们全部忽略，即将x 增加 1。

    在搜索的过程中，如果我们超出了矩阵的边界，那么说明矩阵中不存在 target
    */
    bool findNumberIn2DArray3( vector< vector< int > >& matrix, int target ) {

        int row = matrix.size();
        if ( row == 0 ) {
            return false;
        }

        int column = matrix[ 0 ].size();
        if ( column == 0 ) {
            return false;
        }

        int i = 0, j = column - 1;

        while ( j >= 0 && i < row ) {

            int num = matrix[ i ][ j ];
            if ( num == target ) {
                return true;
            }
            else if ( num < target ) {
                i++;
            }
            else if ( num > target ) {
                j--;
            }
        }
        return false;
    }

    int minArray( vector< int >& numbers ) {
        int len = numbers.size();
        if ( len == 1 ) {
            return numbers[ 0 ];
        }
        for ( int i = 0; i < len - 1; i++ ) {
            if ( numbers[ i ] > numbers[ i + 1 ] ) {
                return numbers[ i + 1 ];
            }
        }

        return numbers[ len - 1 ] < numbers[ 0 ] ? numbers[ len - 1 ] : numbers[ 0 ];
    }

    // 二分法
    int minArray2( vector< int >& numbers ) {
        int i = 0;
        int j = numbers.size() - 1;
        int m;
        while ( i != j ) {
            m = ( i + j ) / 2;
            if ( numbers[ m ] < numbers[ j ] ) {
                j = m;
            }
            else if ( numbers[ m ] > numbers[ j ] ) {
                i = m + 1;
            }
            else if ( numbers[ m ] == numbers[ j ] ) {
                j--;
            }
        }
        return numbers[ i ];
    }

    void QuickSort( vector< int >& a, int begin, int end ) {
        if ( begin > end ) {
            return;
        }

        int i = begin, j = end;
        int pivot = a[ begin ];

        while ( i != j ) {
            while ( a[ j ] >= pivot && i < j ) {
                j--;
            }
            while ( a[ i ] <= pivot && i < j ) {
                i++;
            }
            int temp = a[ i ];
            a[ i ]   = a[ j ];
            a[ j ]   = temp;
        }
        a[ begin ] = a[ i ];
        a[ i ]     = pivot;

        QuickSort( a, begin, i - 1 );
        QuickSort( a, i + 1, end );
    }
};

#endif /*_FIND_*/
